home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Source Code / VirtualDub / sylia / StringHeap.cpp < prev    next >
C/C++ Source or Header  |  2003-10-01  |  4KB  |  163 lines
  1. #include <string.h>
  2. #include <crtdbg.h>
  3.  
  4. #include "ScriptError.h"
  5.  
  6. #include "StringHeap.h"
  7.  
  8. CStringHeap::CStringHeap(long quads, long handles) {
  9.     lpHeap = new StringDescriptor[lQuads = quads];
  10.     lpHandleTable = new char *[lHandles = handles];
  11.  
  12.     if (lpHeap)
  13.         Clear();
  14. }
  15.  
  16. CStringHeap::~CStringHeap() {
  17.     delete[] lpHeap;
  18.     delete[] lpHandleTable;
  19. }
  20.  
  21. void CStringHeap::Clear() {
  22.     lpHeap[0].handle    = NULL;
  23.     lpHeap[0].len        = lQuads-1;
  24.  
  25.     lQuadsFree            = lQuads;
  26.  
  27.     memset(lpHandleTable, 0, sizeof(char **)*lHandles);
  28. }
  29.  
  30. void CStringHeap::Compact() {
  31.     StringDescriptor sd_temp;
  32.     long cur_used = 0, cur_free = 0;
  33.  
  34.     // find first free quad
  35.  
  36.     while(cur_free < lQuads) {
  37.         if (!lpHeap[cur_free].handle)
  38.             break;
  39.  
  40.         cur_free += (lpHeap[cur_free].len&0x0FFFFFFF)/8 + 2;
  41.     }
  42.  
  43.     // heap is full, can't compact...
  44.  
  45.     if (cur_free >= lQuads)
  46.         return;
  47.  
  48.     cur_used = cur_free + lpHeap[cur_free].len + 1;
  49.  
  50.     // only one free block (no compacting needed)?
  51.  
  52.     if (cur_used >= lQuads)
  53.         return;
  54.  
  55.     // begin compaction
  56.  
  57.     while(cur_used < lQuads) {
  58.         long lQuadSize;
  59.  
  60.         if (lpHeap[cur_used].handle) {
  61.  
  62.             // used block... swap it with the free block
  63.  
  64.             lQuadSize = (lpHeap[cur_used].len & 0x0FFFFFFF)/8 + 2;
  65.  
  66.             sd_temp = lpHeap[cur_free];
  67.             memmove(&lpHeap[cur_free], &lpHeap[cur_used], lQuadSize * 8);
  68.             *lpHeap[cur_free].handle = (char *)&lpHeap[cur_free+1];
  69.  
  70.             cur_free += lQuadSize;
  71.             lpHeap[cur_free] = sd_temp;
  72.  
  73.         } else {
  74.  
  75.             // free block... merge it in
  76.  
  77.             lQuadSize = lpHeap[cur_used].len+1;
  78.  
  79.             lpHeap[cur_free].len += lQuadSize;
  80.         }
  81.  
  82.         cur_used += lQuadSize;
  83.     }
  84. }
  85.  
  86. bool CStringHeap::_Allocate(char **handle, int len, bool temp) {
  87.     long lCurQuad = 0;
  88.     long lQuadsNeeded = len/8+1;
  89.  
  90.     _RPT2(0,"_Allocate(%ld) [%ld quads]\n", len, lQuadsNeeded);
  91.  
  92.     while(lCurQuad < lQuads) {
  93.         if (lpHeap[lCurQuad].handle) {
  94.             _RPT4(0,"\t%05ld used - %ld quads (%ld bytes) (%s)\n",
  95.                         lCurQuad,
  96.                         (lpHeap[lCurQuad].len & 0x0FFFFFFF)/8+2,
  97.                         (lpHeap[lCurQuad].len & 0x0FFFFFFF),
  98.                         lpHeap[lCurQuad].len & 0x80000000 ? "temp" : "normal");
  99.  
  100.             lCurQuad += (lpHeap[lCurQuad].len&0x0FFFFFFF)/8 + 2;
  101.         } else if (lpHeap[lCurQuad].len >= lQuadsNeeded) {
  102.             _RPT2(0,"\t%05ld free - %ld quads\n", lCurQuad, lpHeap[lCurQuad].len+1);
  103.  
  104.             if (lpHeap[lCurQuad].len > lQuadsNeeded) {
  105.                 lpHeap[lCurQuad + lQuadsNeeded + 1].handle    = NULL;
  106.                 lpHeap[lCurQuad + lQuadsNeeded + 1].len        = lpHeap[lCurQuad].len-1-lQuadsNeeded;
  107.             }
  108.  
  109.             *handle = (char *)&lpHeap[lCurQuad+1];
  110.             lpHeap[lCurQuad].handle    = handle;
  111.             lpHeap[lCurQuad].len    = temp ? len | 0x80000000 : len;
  112.  
  113.             lQuadsFree -= lQuadsNeeded+1;
  114.             return true;
  115.         } else {
  116.             _RPT2(0,"\t%05ld free - %ld quads\n", lCurQuad, lpHeap[lCurQuad].len+1);
  117.             lCurQuad += lpHeap[lCurQuad].len+1;
  118.         }
  119.     }
  120.     return false;
  121. }
  122.  
  123. char **CStringHeap::Allocate(int len, bool temp) {
  124.     long i;
  125.  
  126.     _RPT1(0,"Allocate: %ld quads free\n", lQuadsFree);
  127.  
  128.     for(i=0; i<lHandles; i++)
  129.         if (!lpHandleTable[i]) break;
  130.  
  131.     if (i>=lHandles)
  132.         SCRIPT_ERROR(OUT_OF_STRING_SPACE);
  133.  
  134.     if (lQuadsFree < len/8+2)
  135.         SCRIPT_ERROR(OUT_OF_STRING_SPACE);
  136.  
  137.     if (_Allocate(&lpHandleTable[i],len,temp)) return &lpHandleTable[i];
  138.  
  139.     Compact();
  140.  
  141.     if (_Allocate(&lpHandleTable[i],len,temp)) return &lpHandleTable[i];
  142.  
  143.     _RPT0(0,"Sylia/StringHeap: should have been able to allocate, but wasn't\n");
  144.     SCRIPT_ERROR(INTERNAL_ERROR);
  145. }
  146.  
  147. void CStringHeap::Free(char **handle, bool temp_only) {
  148.     char *s = *handle;
  149.     StringDescriptor *sdp = (StringDescriptor *)s - 1;
  150.     long lQuads;
  151.  
  152.     if (temp_only && !(sdp->len & 0x80000000))
  153.         return;
  154.  
  155.     lQuads = (sdp->len&0x0FFFFFFF)/8 + 1;
  156.  
  157.     *sdp->handle = NULL;
  158.     sdp->handle = NULL;
  159.     sdp->len    = lQuads;
  160.  
  161.     lQuadsFree += lQuads;
  162. }
  163.